const DEFAULT_BASE = 37;
const DEFAULT_MODULUS = 101;

/**
 * 表示多项式哈希函数的类。
 */
export default class PolynomialHash {
  /**
   * PolynomialHash 类的构造函数。
   *
   * @param {Object} options - 哈希配置选项。
   * @param {number} [options.base=DEFAULT_BASE] - 用于创建多项式的基数。
   * @param {number} [options.modulus=DEFAULT_MODULUS] - 防止哈希溢出的模数。
   */
  constructor({ base = DEFAULT_BASE, modulus = DEFAULT_MODULUS } = {}) {
    this.base = base;
    this.modulus = modulus;
  }

  /**
   * 创建字符串哈希表示的方法。
   *
   * 时间复杂度: O(word.length)。
   *
   * @param {string} word - 需要被哈希的字符串。
   * @return {number} 返回计算得到的哈希值。
   */
  hash(word) {
    const charCodes = Array.from(word).map((char) => this.charToNumber(char));

    let hash = 0;
    for (let charIndex = 0; charIndex < charCodes.length; charIndex += 1) {
      hash *= this.base;
      hash += charCodes[charIndex];
      hash %= this.modulus;
    }

    return hash;
  }

  /**
   * 根据前一个单词向左移动一个字符后的哈希值重新计算新的哈希表示。
   *
   * 重新计算单词的哈希表示以便不必再次遍历整个单词。
   *
   * 时间复杂度: O(1)。
   *
   * @param {number} prevHash - 上一个单词的哈希值。
   * @param {string} prevWord - 上一个单词。
   * @param {string} newWord - 新单词。
   * @return {number} 返回重新计算的哈希值。
   */
  roll(prevHash, prevWord, newWord) {
    let hash = prevHash;

    const prevValue = this.charToNumber(prevWord[0]);
    const newValue = this.charToNumber(newWord[newWord.length - 1]);

    let prevValueMultiplier = 1;
    for (let i = 1; i < prevWord.length; i += 1) {
      prevValueMultiplier *= this.base;
      prevValueMultiplier %= this.modulus;
    }

    hash += this.modulus;
    hash -= (prevValue * prevValueMultiplier) % this.modulus;

    hash *= this.base;
    hash += newValue;
    hash %= this.modulus;

    return hash;
  }

  /**
   * 将字符转换为数字。
   *
   * @param {string} char - 需要转换的字符。
   * @return {number} 返回字符对应的数字。
   */
  charToNumber(char) {
    let charCode = char.codePointAt(0);

    // 检查字符是否包含代理对。
    const surrogate = char.codePointAt(1);
    if (surrogate !== undefined) {
      const surrogateShift = 2 ** 16;
      charCode += surrogate * surrogateShift;
    }

    return charCode;
  }
}
